package com.mlh.dp.knapsackProblem;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

// 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
// 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
// 输入: s = "applepenapple", wordDict = ["apple", "pen"]
// 输出: true
// 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
// 注意，你可以重复使用字典中的单词。

public class WordSplit {

    public static void main(String[] args) {
        List<String> wordDict=new ArrayList<>();
        wordDict.add("leet");
        wordDict.add("code");
        String s="leetcode";
        System.out.println(method1(s,wordDict));
    }

    // 后面学了背包问题，感觉这题目跟背包问题更加贴近，他这个就类似完全背包问题
    //完全背包问题就是把物品放在内循环中，外循环则是背包限制
    //方法二就是这个思想

    //核心思想：构造dp数组  dp[i]表示字符前i个字符（从1开始）能否被字典表示
    //假设dp[j]已知为true , j<i ,则dp[i]=dp[j]+ j-i位置s对应的字符看看在字典中是否存在
    //从dp[1]开始  不断循环求解dp数组  最终获得答案
    public static boolean method1(String s, List<String> wordDict){
        HashSet<String>dict=new HashSet<>(wordDict);
        boolean[] dp=new boolean[s.length()+1];
        dp[0]=true;
        for(int i=1;i<dp.length;i++){
            for(int j=0;j<i;j++){
                if(dp[j]&&dict.contains(s.substring(j,i))){
                    dp[i]=true;
                }
            }
        }
        return dp[dp.length-1];
    }

    //这个方法不是我写的
    //这个方法没有利用hashset
    //利用遍历字典来对dp数组进行赋值
    //他和method1各有优势  如果s长度过长 字典数量较少 那么该方法会比较有优势
    //但是如果字典多 且s长度短则method1会比较好
    public static boolean method2(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for(int i = 1;i <= s.length();i++){
            for(String word : wordDict){
                int len = word.length();
                if(i >= len && dp[i - len] && word.equals(s.substring(i - len,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
